#include <iostream>

enum Color
{
    RED,
    BLACK
};
template <class K, class V>
struct RBTreeNode
{
    RBTreeNode(const pair<K, V> &kv) : _parent(nullptr), _left(nullptr), _right(nullptr), _col(RED), _kv(kv)
    {
    }
    RBTreeNode<K, V> *_parent;
    RBTreeNode<K, V> *_left;
    RBTreeNode<K, V> *_right;
    Color _col;
    std::pair<K, V> _kv;
};
template <class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;

public:
    bool Insert(const std::pair<K, V> &kv)
    {
        // 1.插入为根结点
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node *cur = _root;
        Node *parent = nullptr;
        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(kv);
        if (parent->_kv.first > kv.first)
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }

        // 变色
        while (parent && parent->_col == RED)
        {
            Node *grandfather = parent->_parent;

            // 父亲是爷爷的左孩子
            if (parent == grandfather->_left)
            {
                //     g
                //   p   u
                // c
                Node *uncle = grandfather->_right;

                // 叔叔是红色
                if (uncle && uncle->_col == RED)
                {
                    // 变色
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 继续往上更新处理
                    cur = grandfather;
                    parent = cur->_parent;
                }

                // 叔叔是黑色
                else
                {
                    if (cur == parent->_left)
                    {
                        // 单旋
                        //     g
                        //   p
                        // c
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else
                    {
                        // 双旋
                        //     g
                        //   p
                        //     c
                        RotateL(parent);
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        cur->_col = BLACK;
                    }
                    break;
                }
            }

            // 父亲是爷爷的右孩子
            else
            {
                //     g
                //   u   p
                //          c
                //
                Node *uncle = grandfather->_left;
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    if (cur == parent->_right)
                    {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else
                    {
                        //     g
                        //   u   p
                        //      c
                        //
                        RotateR(parent);
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        cur->_col = BLACK;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;
        return true;
    }

    void RotateL(Node *parent)
    {
        Node *subR = parent->_right;
        Node *subRL = subR->_left;

        parent->_right = subRL;
        subR->_left = parent;

        Node *parentParent = parent->_parent;

        parent->_parent = subR;
        if (subRL)
            subRL->_parent = parent;

        if (_root == parent)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = subR;
            }
            else
            {
                parentParent->_right = subR;
            }

            subR->_parent = parentParent;
        }
    }

    void RotateR(Node *parent)
    {
        Node *subL = parent->_left;
        Node *subLR = subL->_right;

        parent->_left = subLR;
        if (subLR)
            subLR->_parent = parent;

        Node *parentParent = parent->_parent;

        subL->_right = parent;
        parent->_parent = subL;

        if (_root == parent)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
            {
                parentParent->_left = subL;
            }
            else
            {
                parentParent->_right = subL;
            }

            subL->_parent = parentParent;
        }
    }

private:
    Node *_root;
};

int main()
{
    return 0;
}